package baseclass.m_graph;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**图的结构
 * @date 2020/3/6 18:32
 */
public class Graph {
    //顶点：编号和Node，Node：出度、入度、编号、所有要到达的Node、边
    Map<Integer,Node> nodes;
    //边：包括权重、起始点(Node类型)和终止点(Node类型)
    Set<Edge> edges;

    public Graph() {
        nodes = new HashMap<>();
        edges = new HashSet<>();
    }
    public static Graph createGraph(Integer[][] matrix) {
        Graph graph = new Graph();
        //一个3*N的矩阵描述图的信息，每一行代表[weight,from,to]
        for (int i = 0; i < matrix.length; i++) {
            //权重
            Integer weight = matrix[i][0];
            //起始点
            Integer from = matrix[i][1];
            //终点
            Integer to = matrix[i][2];

            //如果没有当前节点，则新建节点
            if (!graph.nodes.containsKey(from)) {
                //新建其实节点
                graph.nodes.put(from, new Node(from));
            }
            //如果没有当前节点，则新建节点
            if (!graph.nodes.containsKey(to)) {
                //新建终止节点
                graph.nodes.put(to, new Node(to));
            }

            Node fromNode = graph.nodes.get(from);
            Node toNode = graph.nodes.get(to);
            //把边的信息填充
            Edge newEdge = new Edge(weight, fromNode, toNode);
            //更新起始节点和终止节点的数组
            fromNode.nexts.add(toNode);
            fromNode.out++;
            toNode.in++;
            //起始点添加边信息
            fromNode.edges.add(newEdge);
            graph.edges.add(newEdge);
        }
        return graph;
    }
}
